/**
题目:
给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
进阶：
如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。
示例：
输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 8 -> 0 -> 7
思路:
    计算长度 递归运算
效果:
    执行用时：16 ms, 在所有 Go 提交中击败了46.15%的用户
    内存消耗：4.9 MB, 在所有 Go 提交中击败了72.19%的用户
*/

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    var d1,d2 int
    a,b := l1,l2
    for a != nil{
        d1 ++
        a = a.Next
    }
    for b != nil{
        d2 ++
        b = b.Next
    }
    res,c:= addTwoNumbers2(l1,l2,d1,d2)
    if c > 0{
        return &ListNode{Val:c,Next:res}
    }
    return res
} 
func addTwoNumbers2(l1,l2 *ListNode,d1,d2 int )(res *ListNode,c int){
        if l1 != nil && l2 != nil{
            if l1.Next == nil && l2.Next == nil{
                n := l1.Val + l2.Val
                c = n / 10
                res = &ListNode{Val:n % 10,Next:nil}
                return
            }
        }
        var a *ListNode
        var b,n int
        if d1 > d2{
            a, b = addTwoNumbers2(l1.Next,l2,d1-1,d2)
            n = l1.Val + b
        }else if d1 < d2{
            a, b = addTwoNumbers2(l1,l2.Next,d1,d2-1)
            n = l2.Val + b
        }else{
            a, b = addTwoNumbers2(l1.Next,l2.Next,d1-1,d2-1)
            n = b + l1.Val + l2.Val
        }
        res = &ListNode{Val:n % 10,Next:a}
        c = n / 10
        return 
}